#include<stdio.h>
#include<stdlib.h>
struct node
{ int val;
  struct node *next;
} *beg;// beg points at the beginning of the list




int menu()
{
	int choice;
	printf("\t\t******LIST Implementation Using Linked List******\n");
	printf("\t0. Append\n\t1. Display\n\t2. Extend\n\t3. insert_beg\n\t4. Delete\n\t5. Index\n\t6. Count\n\t7. Reverse\n\t8. Insert\n\t9  Pop\n\t10.  Exit\n\t\tEnter your choice : ");
	scanf("%d", &choice);
	printf("\n\n");
	return choice;
}


//to create initial set of elements
void append(int elm)
{ struct node *new_node,*current,*tmp;
  new_node=malloc(sizeof(struct node));
  new_node->val=elm;
  new_node->next=NULL;
  
  if(beg==NULL)
  {  beg=new_node;
     current=new_node;
  }
  else
  { tmp=beg;
  while(tmp->next!=NULL)
  {tmp=tmp->next;
  }
  tmp->next=new_node;
  }
}
// displaying the list
void display(struct node *r)
  {
      r=beg;
      if(r==NULL)
     {
       printf("[]");
       return;
     }
      printf("["); 

       while(r!=NULL)
    {
      printf("%d ",r->val);
      r=r->next;
    }
     printf("]");
  }

//function to extend the list by appending all the items in the given list
void extend(void)
{
	int len,i,num;
	printf("\n \n Enter the number of elements in the list : ");
	scanf("%d",&len);
	for (i = 0; i < len; i++)
	{
		printf("Enter element[%d] of the list to be appended :",i+1);
		scanf("%d",&num);
		append(num);
	}
}


void delete(int x)
{   
     struct node *temp, *m;
     temp=beg;
      while(temp!=NULL)
    {
       if(temp->val==x)
       {   
           if(temp==beg)
           {
              beg=temp->next;
              free(temp);
              return;
           }
           else
         {
           m->next=temp->next;
           free(temp);
           return;
         }
      }else
        {
           m=temp;
          temp= temp->next;
        }

}
 printf("\n element not found!!:");

} 

int length()
 {
   struct node *n;
   int c=0;
   n=beg;
    while(n!=NULL)
   {
     n=n->next;
     c++;
   }
  return(c);
 }


//insert a node at the begining
void insert_beg(int x)
{
   struct node *temp;
   temp=malloc(sizeof(struct node));
   temp->val=x;
   if ( beg== NULL)
   {
         beg=temp; 
         beg->next=NULL;
   }
   else
   {
         temp->next=beg;
         beg=temp;
   }
}
int index1(int x)
{ struct node *p;
  int i;
  int count=0;
  p=beg;
  while(p->val!=x)
    
  {   count++;
      p=p->next;
      
   }
  count++;
  return(count);
}
	
int count(int num)
{ int c=0;
  struct node *temp;
  temp=beg;
  while(temp!=NULL)
  { if(temp->val==num)
     { c++;
       temp=temp->next;
      }
    else
    { temp=temp->next;
     }
   } 
  return c;
  
} 
//reversing the list
void reverse(struct node *temp)
{
   struct node *m, *n,*l,*s;
   m=temp;
   n=NULL;
  while(m!=NULL)
 {
   s=n;
   n=m;
  m=m->next;
  n->next=s;
 }
   beg=n;
   printf("\n reversed list is:-->");
   display(beg);
}
void insert(int n,int x)
{
  int c=0;
  if((x>length()) || (x<0))
  {
    printf("Index out of range\n");
    exit(0);
  }
  
  struct node *new,*i,*j;
  new=malloc(sizeof(struct node));
  new->val=x;
  if(x==0)
  {
    new->next=beg;
    beg=new;
  }
  else
  {
   for(i=beg;i!=NULL;i=i->next)
   {
    j=i;
    ++c;
    if(c==x)
    {
      break;
    }
  }
  new->next=j->next;
  j->next=new;
  }
  
}

void pop(int i)
{

  int l;
  struct node *j,*k;
  char c;
  printf("Do you want to enter an index number? ");
  scanf(" %c",&c);

  if(c=='y'|| c=='Y')
 {
  if(i>length() || i<0)
  {
     printf("Index out of range\n");
    exit(0);
  }
  if(i==0)
  {
    printf("Element popped=%d\n",beg->val);
    beg=beg->next;
  }
  else
  {
    j=beg;
    for(l=1;l<i;l++)
   {
     j=j->next;
   }
   printf("Element popped=%d\n",j->next->val);
   j->next=j->next->next;  
 }
 }
 else
 {
   for(k=beg;k->next->next!=NULL;k=k->next)
   {;}
   k->next=NULL;
 }
 printf("New list is: ");
 for(j=beg;j!=NULL;j=j->next)
  {
    printf("%d ",j->val);
  }
  printf("\n");
 
}

void main()
{
	int choice,elm;
        beg=NULL;
        struct node *n;
	while(1)
	{
		choice = menu();
		switch (choice)
		{
			case 0:
				printf("Enter an element : ");
				scanf("%d", &elm);
				append(elm);
				break;
			
			case 1:
				 display(n);
				 break;
                        case 2: extend();
                                break;
                        case 3: {
                                int x;
                                printf(" \nenter the element to be inserted at the beginning of the list:");
                                scanf("%d", &x);
                                insert_beg(x);
                                break;}
                        case 4: { int x;
                                  printf("\n enter element to be deleted:");
                                  scanf("%d",&x);
                                  delete(x);
                                  break;
                                }
                        case 5: { int num,e;
                			printf("\nenter the number whose index you want to find:");
                			scanf("%d",&num);
                			e=index1(num);
                			printf("\n index of %d is=%d",num,e);
                			break;
               			}
                        case 6: { int num,e;
                                  printf(" \n enter the number whose count you want to find:");
                                  scanf("%d",&num);
                                  e=count(num);
                                   printf("\nnumber of times %d appears is-->%d",num,e);
                                  break;
                                 }
                        case 7: reverse(beg);
                        case 8: { int i,num;
                                  printf("\n enter element to be inserted:");
                                  scanf("%d",&num);
                                  printf("\n enter location:");
                                  scanf("%d",&i);
                                  insert(num,i);
                                  break;
                                 }
                        case 9:   {int i;
                                  printf("\n enter the index number you want to pop:");
                                  scanf("%d",&i);
                                  pop(i);
                                  break;
                                  }
			case 10: exit(0);
			
                        default:
				printf("Invalid Choice!!");
		}
	}
}
// end!!!
